package com.leetcode.algs4.graph.least_path;

import com.leetcode.algs4.graph.mst.IndexMinPQ;

import java.util.Stack;

/**
 * @author Dennis Li
 * @date 2020/6/19 9:42
 */
public class DijkstraSP {

    private DirectedEdge[] edgeTo;
    private double[] distTo;
    private IndexMinPQ<Double> pq;

    public DijkstraSP(EdgeWeightedDigraph G, int s) {

        edgeTo = new DirectedEdge[G.V()];
        distTo = new double[G.V()];
        pq = new IndexMinPQ<>(G.V());

        for (int v = 0; v < G.V(); v++) {
            // 每一个都要赋初值
            distTo[v] = Double.POSITIVE_INFINITY;
            // 每一次都需要添加树的顶点进队列，相当于每次找最短路径都会从顶点开始走一遍
            distTo[s] = 0.0;
            pq.insert(s, 0.0);
            while (!pq.isEmpty()) {
                // 放松pq权值最小的点
                relax(G, pq.delMin());
            }
        }
    }

    private void relax(EdgeWeightedDigraph G, int v) {
        for (DirectedEdge e : G.adj(v)) {
            int w = e.to();
            if (distTo[w] > distTo[v] + e.weight()) {
                // 松弛边
                distTo[w] = distTo[v] + e.weight();
                edgeTo[w] = e;
                // 修改优先队列中对应的值
                if (pq.contains(w)) pq.changeKey(w, distTo[w]);
                else pq.insert(w, distTo[w]);
            }
        }
    }

    public double distTo(int v) {
        validateVertex(v);
        return distTo[v];
    }

    public boolean hasPathTo(int v) {
        validateVertex(v);
        return distTo[v] < Double.POSITIVE_INFINITY;
    }

    public Iterable<DirectedEdge> pathTo(int v) {
        validateVertex(v);
        if (!hasPathTo(v)) return null;
        Stack<DirectedEdge> path = new Stack<>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
            path.push(e);
        }
        return path;
    }

    // 验证点是否在树中
    private void validateVertex(int v) {
        int V = distTo.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
    }
}
